package lc20240622;

import java.util.Arrays;
import java.util.PriorityQueue;

public class MaxFit {
    public int maxProfit(int[] capital, int[] profits, int k, int w) {
        int n = profits.length;
        // 根据所需资本从小到大排序
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);

        // 大顶堆，用于存储当前可选择的项目的纯利润
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        int idx = 0;
        for (int i = 0; i < k; i++) {
            while (idx < n && projects[idx][0] <= w) {
                pq.offer(projects[idx][1]);
                idx++;
            }
            if (!pq.isEmpty()) {
                w += pq.poll();
            } else {
                break;
            }
        }

        return w;
    }
}
